package primary.code05_Tree;

import java.util.Stack;

/**
 * 二叉树前、中、后序遍历问题
 * <p>
 * 递归实现、循环实现
 * <p>
 * https://leetcode.cn/problems/binary-tree-inorder-traversal/submissions/598607319/
 */
public class Code01_BinaryTreeTraversal {

    /**
     * 递归前、中、后遍历
     *
     * @param root
     */
    private static void recursivePreOrder(Node root) {
        if (root == null) return;
        System.out.print("  " + root.data);
        recursivePreOrder(root.left);
        recursivePreOrder(root.right);
    }

    private static void recursiveInOrder(Node root) {
        if (root == null) return;
        recursiveInOrder(root.left);
        System.out.print("  " + root.data);
        recursiveInOrder(root.right);
    }

    private static void recursivePostOrder(Node root) {
        if (root == null) return;
        recursivePostOrder(root.left);
        recursivePostOrder(root.right);
        System.out.print("  " + root.data);
    }

    private static void recursivePreOrderTest(Node root) {
        if (root == null) return;
        System.out.print("    " + root.data);
        recursivePreOrderTest(root.left);
        recursivePreOrderTest(root.right);
    }

    private static void recursiveInOrderTest(Node root) {
        if (root == null) return;
        recursiveInOrderTest(root.left);
        System.out.print("    " + root.data);
        recursiveInOrderTest(root.right);
    }

    private static void recursivePostOrderTest(Node root) {
        if (root == null) return;
        recursivePostOrderTest(root.left);
        recursivePostOrderTest(root.right);
        System.out.print("    " + root.data);
    }

    /**
     * 循环前、中、后序遍历
     *
     * @param root
     */
    private static void iterativePreOrder(Node root) {
        if (root == null) return;
        Stack<Node> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                System.out.print("  " + root.data);
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            root = root.right;
        }
    }

    private static void iterativePreOrderTest(Node root) {
        if (root == null) return;
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        Node cur = null;
        while (!stack.isEmpty()) {
            cur = stack.pop();
            System.out.print("  " + cur.data);
            if (cur.right != null) stack.push(cur.right);
            if (cur.left != null) stack.push(cur.left);
        }
    }

    private static void iterativeInOrder(Node root) {
        if (root == null) return;
        Stack<Node> stack = new Stack<>();
        Node cur = root;
        while (cur != null || !stack.isEmpty()) {//存在历史根节点，或存在当前根节点
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                Node push = stack.pop();
                System.out.print("  " + push.data);
                cur = push.right;
            }
        }
    }

    static class NodeFlag {
        Node node;
        int flag;

        public NodeFlag(Node node, int flag) {
            this.node = node;
            this.flag = flag;
        }
    }

    private static void iterativeInOrderTest(Node root) {
        if (root == null) return;
        Stack<NodeFlag> stack = new Stack<>();
        stack.push(new NodeFlag(root, 1));
        while (!stack.isEmpty()) {
            NodeFlag cur = stack.pop();
            if (cur.flag == 1) {
                if (cur.node.right != null) stack.push(new NodeFlag(cur.node.right, 1));
                stack.push(new NodeFlag(cur.node, 2));
                if (cur.node.left != null) stack.push(new NodeFlag(cur.node.left, 1));
            } else {
                System.out.print("," + cur.node.data);
            }
        }
    }

    private static void iterativePostOrder(Node root) {
        if (root == null) return;
        Stack<Node> stack1 = new Stack<>();//存储经历的节点
        Stack<Node> stack2 = new Stack<>();//存储"前序"遍历的节点
        while (root != null || !stack1.isEmpty()) {
            while (root != null) {
                stack1.push(root);
                stack2.push(root);
                root = root.right;
            }
            root = stack1.pop();
            root = root.left;
        }
        while (!stack2.isEmpty()) {
            System.out.print("  " + stack2.pop().data);
        }
    }

    private static void iterativePostOrderTest(Node root) {
        if (root == null) return;
        Stack<Node> stack = new Stack<>();
        Stack<Node> stackReverse = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node cur = stack.pop();
            stackReverse.push(cur);
            if (cur.left != null) {
                stack.push(cur.left);
            }
            if (cur.right != null) {
                stack.push(cur.right);
            }
        }

        while (!stackReverse.isEmpty()) {
            System.out.print("    " + stackReverse.pop().data);
        }
    }

    public static void main(String[] args) {
        //构造树结构测试用
        Node a = new Node(1);
        Node b = new Node(2);
        Node c = new Node(3);
        Node d = new Node(4);
        Node e = new Node(5);
        Node f = new Node(6);
        Node g = new Node(7);
        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        c.left = f;
        c.right = g;

        //递归
        System.out.println("recursice pre order: ");
        recursivePreOrderTest(a); //     1    2    4    5    3    6    7
        System.out.println();
        System.out.println("recursice in order: ");
        recursiveInOrderTest(a); //     4    2    5    1    6    3    7
        System.out.println(); //
        System.out.println("recursice post order: ");
        recursivePostOrderTest(a); //     4    5    2    6    7    3    1
        System.out.println();

        //循环
        System.out.println("iterative pre order: ");
        iterativePreOrderTest(a); //     1    2    4    5    3    6    7
        System.out.println();
        System.out.println("iterative in order: ");
        iterativeInOrder(a); //     4    2    5    1    6    3    7
        System.out.println();
        System.out.println("iterative post order: ");
        iterativePostOrderTest(a); //     4    5    2    6    7    3    1
        System.out.println();
    }
}
